The present invention relates generally to cryptographic methods and systems to be used in digital data processing and, in particular, is directed to methods and systems for public key distribution.
Key management and distribution is an extremely important aspect of secure communications systems based on cryptographic methods. Even the most secure cryptographic algorithm instantly becomes insecure if the corresponding keys fall into the wrong hands. In fact, cryptanalysts and hackers alike frequently begin the exploitation of cryptosystems by attempting to obtain and exploit the keys, since this is often easier and more cost efficient. As a result, much attention has been given to devising cryptographic methods and systems that allow secure, but simple, distribution of cryptographic key information.
Early concerns for key distribution lead to the invention of public-key cryptography. Public-key cryptographic algorithms employ an encryption key that is different from the decryption key. Since the algorithms are designed so that it is computationally infeasible to determine the decryption key from the encryption key, the encryption key can be made “public.” Anyone may use a public encryption key to encrypt a message, but only a recipient with the corresponding “private” key may decrypt the message.
The first algorithm for generalized public-key encryption was the knapsack algorithm developed by Ralph Merkle and Martin Hellman. Knapsack algorithms get their security from the knapsack problem. Given a one-dimensional knapsack of length S and n rods of lengths a1, a2, . . . ,an, the “knapsack problem” is to find a subset of rods which exactly fill the knapsack, if such a subset exists. An equivalent way of expressing the knapsack problem is to find a binary n-vector x such that S=a*x, if such an x exists. When used in vector notation, the mathematical symbol “*” means to compute the dot product of two or more vectors. In the knapsack problem, finding a solution, x, is widely believed to be an NP-complete problem, and so is presumed to be difficult.
Mathematical problems classified as “NP-complete” are believed to be so mathematically complex as to be solvable in polynomial time only on a non-deterministic Turing machine or, in other words, by exhaustively trying all possible solutions. For additional discussion of NP-completeness and complexity theory, see Michael R. Gray and David S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” (W. H. Freeman and Co. 1979). Cryptographic algorithms that are NP-complete, therefore, are generally resistant to brute-force exhaustive attacks.
In their paper, Merkle and Hellman proposed a public key system that was derived by creating instances of the knapsack problem that could be solved if certain secret information was known. See Ralph C. Merkle and Martin Hellman, “Hiding Information and Signatures in Trapdoor Knapsaks,” IEEE Transactions on Information Theory, v. 24, n. 5, September 1978, pp. 525-530. Unfortunately, this system proved to be less secure than the general (unrestricted) knapsack problem. See Leonard M. Adelman, “On Breaking the Iterated Merkle-Hellman Public Key Cryptosystem”, Advances in Cryptology Proceedings of Crypto '82, Plenum Press 1983, pages 303-308; Ernest F. Brickell, “Breaking iterated knapsacks.” Advances in Cryptology, Proceedings of Crypto '84, Springer Verlag, 1985, pp. 342-358.
Public-key cryptographic systems solve the key distribution problem, however, most are computationally intensive and therefore slow to operate on conventional computer systems. One of the most frequently used public-key cryptosystems, the RSA cryptographic algorithm, for example, requires integer exponentiation with moduli that are often in excess of 1,000 bits.
Therefore, a need exists for secure cryptographic methods and systems that both are computationally more efficient than conventional systems yet also solve the key distribution and management problems of conventional approaches.